public class MySingleList {
    //将节点定义为一个静态内部类
    static class ListNode {
        public int val;//节点的成员属性，值
        public ListNode next;//结点的成员属性，用来存放节点的地址

        public ListNode(int val) {
            this.val = val;//定义一个构造方法，用来初始化节点，这里只构造值，不构造next是因为我创建一个节点以后，值是由我自己来给，但是next存放
            //下一个节点的地址，下一个节点的地址是什么我也不确定，所以给不了。
        }
    }

    public ListNode head;//定义一个头节点，用来存放头结点的地址
    //翻转链表
    public ListNode reverseList(){
        //1.先判断链表是否为空
        if (head == null) {
            return null;
        }
        //2.只有一个节点
        if(head.next==null){
            return head;
        }
        //3.至少有2个节点
        ListNode cur=head.next;//cur记录下head下一个节点的地址
        head.next=null;//将head.next置为空
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }
    //找中间节点(s=v*t)
    public int middleNode(){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;//fast走两步
            slow=slow.next;//slow走一步
        }
        return slow.val;//此时slow所在位置就是链表的中间节点
    }
    //返回第K个节点
    public int FindKthToTail(int k){
        //1.判断k位置的合法性
        if(k<=0||head==null){
            return -1;
        }
        if(head==null){
            return 0;
        }
        ListNode fast=head;
        ListNode slow=head;
        int count=0;
        while (count!=k-1){
            fast=fast.next;
            if(fast==null){
                return -1;
            }
            count++;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);//创建一个节点对象，用来头插
        node.next=head;
        head=node;
    }
    //遍历节点
    public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }
    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;
            return;
        }
        ListNode cur=this.head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //任意位置插入
    public void addIndex(int index,int data){
        //1.先检查index位置的合法性
        checkPos(index);
        //2.index位置为0时为头插法
        if (index==0){
            addFirst(data);
            return;//不要忘记return,不然后面的语句还会执行
        }
        //index位置为size()时，为尾插法
        if(index==size()){
            addLast(data);
            return;//不要忘记return,不然后面的语句还会执行
        }
        //其他任意位置插入
        ListNode cur=FindIndex(index);
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    //求链表元素的个数
    public int size(){
        int count=0;//定义一个计数器，用来统计遍历到的元素个数
        ListNode cur=this.head;//让cur代替head去遍历链表，因为用head去遍历链表，最后变成空，链表就没有头节点，也就找不到链表了
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    private ListNode FindIndex(int index) {
        ListNode cur=head;
        int count=0;
        while (count!=index-1){
            count++;
            cur=cur.next;
        }
        return cur;
    }

    private void checkPos(int index) {
        if(index<0||index>size()){
            throw new IndexException("index给的不合法");
        }
    }
}